/**
 * Created by L.jp
 * Description:统计一个数字在排序数组中出现的次数。
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出:2
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0

 * User: 86189
 * Date: 2022-02-25
 * Time: 20:04
 */
/*
*  思路:   利用二分法先定位区间，找到目标值可能出现在数组的下标范围，然后再从新的区间进行计数
*
* */
public class Solution {
    public static int search(int[] nums, int target) {
        int left=0;
        int right=nums.length; //返回值{1}，目标值为1这种情况
        int ret=0; //次数
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid;
            }else{   //定位到目标值，然后从新的[left,right]去查找这个数字并且计数
                while(left < right){
                    if(nums[left]==target){
                        ret++;
                    }
                    left++;  //不管left的值等不等于目标值，left都要++
                }
                //当left=right时，也跟外层循环的条件一样，然后退出循环，返回计数结果
            }
        }
        return ret;

    }

    public static void main(String[] args) {
        int[] nums={1,1,2,3,4};
        int target=5;
        System.out.println(search(nums, target));
    }
}
